{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #打家劫舍"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rob"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #打家劫舍"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，<strong>如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警</strong>。</p>\n",
    "\n",
    "<p>给定一个代表每个房屋存放金额的非负整数数组 <code>nums</code>&nbsp;，请计算<strong>&nbsp;不触动警报装置的情况下 </strong>，一夜之内能够偷窃到的最高金额。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums =<strong> </strong>[1,2,3,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。\n",
    "&nbsp;    偷窃到的最高金额 = 1 + 3 = 4 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums =<strong> </strong>[2,7,9,3,1]\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。\n",
    "&nbsp;    偷窃到的最高金额 = 2 + 9 + 1 = 12 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 400</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 198&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/house-robber/\">https://leetcode-cn.com/problems/house-robber/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Gu0c2T](https://leetcode.cn/problems/Gu0c2T/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Gu0c2T](https://leetcode.cn/problems/Gu0c2T/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]', '[2,7,9,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        global memo \n",
    "        global arr \n",
    "        arr = nums \n",
    "        # state dp[i][mod]: maximum sum of nums[0..i] with mod ,mod = 0, 1,2\n",
    "        n = len(nums)\n",
    "        memo = [[-1]*3 for _ in range(n)]\n",
    "        res = dp(n-1,0)\n",
    "        # print(memo)\n",
    "        if res == -float('inf'):\n",
    "            return 0 \n",
    "        return res \n",
    "\n",
    "memo = []\n",
    "arr = []\n",
    "def dp(i: int, m: int ) -> int:\n",
    "    global memo \n",
    "    global arr \n",
    "    # print(i,m)\n",
    "    if memo[i][m] != -1:\n",
    "        return memo[i][m]\n",
    "\n",
    "    # base cases \n",
    "    if i == 0:\n",
    "        if arr[0]%3 == m:\n",
    "            memo[i][m] = arr[0] \n",
    "        else:\n",
    "            memo[i][m] = 0\n",
    "        return memo[i][m]\n",
    "    # state transition \n",
    "    # dp(i,m) = dp(i-1,m-curMod) + arr[i]\n",
    "    # res = 0 \n",
    "    curMod = arr[i]%3 \n",
    "    prevMod = 0 \n",
    "\n",
    "    res = dp(i-1,m)\n",
    "    # try 3 cases  \n",
    "    \n",
    "    # res = max(dp(i-1,m),dp(i-1, (3+m-curMod)%3) + arr[i])\n",
    "    if curMod == m:\n",
    "        # choose this the number only\n",
    "        res = max(res,arr[i])\n",
    "    subproblem =  dp(i-1,(3+m-curMod)%3)\n",
    "    if subproblem !=0:\n",
    "        res = max(res,subproblem + arr[i])\n",
    "    \n",
    "    # res = max(dp(i-1,m), dp(i-1,(3+m-curMod)%3) + arr[i])\n",
    "    # res = max(res,0)\n",
    "\n",
    "    # save result \n",
    "    memo[i][m] = res \n",
    "    return memo[i][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gridGame(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        # traverse the position where robot A makes a turn\n",
    "        # j = 0 ... n-1\n",
    "        # [0,j]      [j,n-1]\n",
    "        # s[0][:j+1] s[1][j:]\n",
    "        # 则robotB 剩下的选择是 max( s[0][j+1:], s[1][:j] )\n",
    "        n = len(grid[0])\n",
    "        ps0 = [0]*(n+1)\n",
    "        ps1 = [0]*(n+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            ps0[i+1] = ps0[i] + grid[0][i]\n",
    "            ps1[i+1] = ps1[i] + grid[1][i]\n",
    "        \n",
    "        res = inf\n",
    "        for j in range(0, n):\n",
    "            # max( s[0][j+1:], s[1][:j] )\n",
    "            top = ps0[n] - ps0[j+1]\n",
    "            down = ps1[j]\n",
    "            res = min(res, max(top, down))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:\n",
    "        # use dic\n",
    "        dic = {}\n",
    "        res = []\n",
    "\n",
    "        for i, v in enumerate(groupSizes):\n",
    "            if v not in dic:\n",
    "                dic[v] = []\n",
    "            dic[v].append(i)\n",
    "\n",
    "            if len(dic[v]) == v:\n",
    "                res.append(dic[v])\n",
    "                dic[v] = []\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2, len(nums)):\n",
    "            dp[i] = max(dp[i-2]+nums[i], dp[i-1])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        ans = [ 0 for _ in range(len(nums))]\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        ans[0] = nums[0]\n",
    "        ans[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            ans[i] = max(ans[i-1],ans[i-2]+nums[i])\n",
    "        return ans[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        total=n*[0]\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                total[i]=nums[i]\n",
    "            elif i==1:\n",
    "                total[i]=max(total[i-1],nums[i])\n",
    "            else:\n",
    "                total[i]=max(total[i-1],total[i-2]+nums[i])\n",
    "        return max(total)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        f0 = f1 = 0\n",
    "        for i in nums:\n",
    "            f0,f1 = f1,max(f1,f0 + i)\n",
    "        return f1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # dp[i] 前i家最大值（不包括i）\n",
    "        dp = [0 for _ in range(len(nums)+1)]\n",
    "        dp[1] = nums[0]\n",
    "        for i in range(2,len(nums)+1):\n",
    "            dp[i] = max(dp[i-2]+nums[i-1], dp[i-1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        dp = [nums[0]] + [max(nums[0], nums[1])] + [0 for _ in range(len(nums)-2)]\n",
    "        for i in range(2, len(nums)):\n",
    "            dp[i] = max(dp[i-1], dp[i-2]+nums[i])\n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 2:\n",
    "            return max(nums)\n",
    "        res = [0] * len(nums)\n",
    "        res[0], res[1] = nums[0], max(nums[1], nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            res[i] = max(res[i-1], res[i-2]+nums[i])\n",
    "            \n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        prevTwoHouse = nums[0]\n",
    "        prevHouse = max(nums[0], nums[1])\n",
    "        currHouse = 0\n",
    "\n",
    "        for i in range(2, n):\n",
    "            currHouse = max(prevTwoHouse + nums[i], prevHouse)\n",
    "            prevTwoHouse = prevHouse\n",
    "            prevHouse = currHouse\n",
    "\n",
    "        return max(prevTwoHouse, prevHouse)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        if n == 1: return nums[0]\n",
    "        dp = [0]* (n)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(0 + nums[1],dp[0])\n",
    "        for i in range(2,n):\n",
    "            dp[i] = max(dp[i-1], dp[i-2]+nums[i])\n",
    "        return dp[-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # 边界值处理\n",
    "        if(len(nums) == 0):\n",
    "            return 0\n",
    "        elif(len(nums) == 1):\n",
    "            return nums[0]\n",
    "        \n",
    "        dp1 = 0    # 不抢第i家的最大收益\n",
    "        dp2 = nums[0]   # 抢第i家的最大收益\n",
    "        for v in nums[1:]:\n",
    "            new_dp1 = max(dp1, dp2)\n",
    "            dp2 = dp1 + v\n",
    "            dp1 = new_dp1\n",
    "        \n",
    "        return max(dp1, dp2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, words: List[int]) -> int:\n",
    "        if len(words) == 1:\n",
    "            return words[0]\n",
    "        money = [0 for i in range(len(words))]\n",
    "        money[0] = words[0]\n",
    "        money[1] = max(words[0], words[1])\n",
    "        for i in range(2, len(words)):\n",
    "            money[i] = max(money[i-1], money[i-2]+words[i])\n",
    "        return money[len(words)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return max(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[:2])\n",
    "\n",
    "\n",
    "        for i in range(2,n):\n",
    "            dp[i] = max(nums[i] + dp[i-2], dp[i-1])\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # f = [0] * (n+2)\n",
    "        f0 = f1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            f2 = max(f1, f0+x)\n",
    "            f0 = f1\n",
    "            f1 = f2\n",
    "        return f2\n",
    "\n",
    "        # if n == 2:\n",
    "        #     return max(nums[0], nums[1])\n",
    "        # elif n == 1:\n",
    "        #     return nums[0]\n",
    "\n",
    "        # @cache\n",
    "        # # cache = [-1] * n\n",
    "        # def dfs(i: int) -> int:\n",
    "        #     # if i == 0:\n",
    "        #     #     return nums[0]\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "\n",
    "        #     # if cache[i] != -1:\n",
    "        #     #     return cache[i]\n",
    "\n",
    "        #     res = max(dfs(i-1), dfs(i-2)+nums[i])\n",
    "        #     # cache[i] = res\n",
    "\n",
    "        #     return res\n",
    "\n",
    "        # return dfs(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # 分别存储上一次和上上次的值\n",
    "        f0,f1 = 0,0\n",
    "        for i in range(len(nums)):\n",
    "            new_f = max(f0+nums[i],f1)\n",
    "            f0 = f1\n",
    "            f1 = new_f\n",
    "        return f1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # n=len(nums)\n",
    "        # sum1=0\n",
    "        # sum2=0\n",
    "        # if n==0:\n",
    "        #     return 0\n",
    "        # if n==1:\n",
    "        #     return nums[0]\n",
    "        # if n==2:\n",
    "        #     if nums[0]>=nums[1]:\n",
    "        #         return nums[0]\n",
    "        #     else:\n",
    "        #         return nums[1]\n",
    "        # else:\n",
    "        #     for i in range(0,n,2):\n",
    "        #         sum1+=nums[i]\n",
    "        #     for i in range(1,n,2):\n",
    "        #         sum2+=nums[i]\n",
    "        #     if sum1>=sum2:\n",
    "        #         return sum1\n",
    "        #     else:\n",
    "        #         return sum2\n",
    "        # n=len(nums)\n",
    "        # dp=[0]*n\n",
    "        # if n<=0:\n",
    "        #     return 0\n",
    "        # if n>=1:\n",
    "        #     dp[0]=nums[0]\n",
    "        # if n>=2:\n",
    "        #     dp[1]=max(nums[0],nums[1])\n",
    "        # for i in range(2,n):\n",
    "        #     dp[i]=max(dp[i-2]+nums[i],dp[i-1])\n",
    "        # return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        if n<0:\n",
    "            return 0\n",
    "        if n>=1:\n",
    "            dp[0]=nums[0]\n",
    "        if n>=2:\n",
    "            dp[1]=max(nums[0],nums[1])\n",
    "        for i in range(2,n):\n",
    "            dp[i]=max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        prevTwoHouse = nums[0]\n",
    "        prevHouse = max(nums[0], nums[1])\n",
    "        currHouse = 0\n",
    "\n",
    "        for i in range(2, n):\n",
    "            currHouse = max(prevTwoHouse + nums[i], prevHouse)\n",
    "            prevTwoHouse = prevHouse\n",
    "            prevHouse = currHouse\n",
    "\n",
    "        return max(prevTwoHouse, prevHouse)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                dp[i] = nums[i]\n",
    "            elif i == 1:\n",
    "                dp[i] = max(dp[i-1], nums[i])\n",
    "            else:\n",
    "                dp[i] = max(dp[i-1], dp[i-2] + nums[i])\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        #dp[j]表示考虑下标j，所能偷盗的最高金额\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=nums[0]\n",
    "        dp[1]=max(nums[0],nums[1])\n",
    "        for j in range(2,n):\n",
    "            dp[j]=max(dp[j-1],dp[j-2]+nums[j])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return max(nums)\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        dp[0][1] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][1]\n",
    "            dp[i][1] = max(dp[i-1][0], dp[i-2][1], dp[i-2][0]) + nums[i]\n",
    "        return max(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "\n",
    "        for i in range(2,n):\n",
    "            dp[i] = max(dp[i-1], dp[i-2] + nums[i])\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        size = len(nums)\n",
    "        if size == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        first, second = nums[0], max(nums[0], nums[1])\n",
    "        for i in range(2, size):\n",
    "            first, second = second, max(first + nums[i], second)\n",
    "        \n",
    "        return second\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        size = len(nums)\n",
    "        if size == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        first, second = nums[0], max(nums[0], nums[1])\n",
    "        for i in range(2, size):\n",
    "            first, second = second, max(first + nums[i], second)\n",
    "        \n",
    "        return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        f0 = f1 = 0\n",
    "        for x in nums:\n",
    "            f0, f1 = f1, max(f1, f0 + x)\n",
    "        return f1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:return nums[0]\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0], dp[1] = nums[0], max(nums[0], nums[1])\n",
    "        for i in range(2, len(nums)):\n",
    "            dp[i] = max(dp[i-1], dp[i-2]+nums[i])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        elif n == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        else:\n",
    "            dp[0] = nums[0]\n",
    "            dp[1] = max(nums[1], nums[0])\n",
    "            for i in range(2, n):\n",
    "                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])\n",
    "            return max(dp[n-2], dp[n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        DP = [[0] * 2 for _ in range(N+1)]\n",
    "\n",
    "        for i in range(1, N+1):\n",
    "            num = nums[i-1]\n",
    "            # rob this rome\n",
    "            DP[i][0] = num + DP[i-1][1]\n",
    "            # do not rob rome\n",
    "            DP[i][1] = max(DP[i-1][1], DP[i-1][0])\n",
    "        return max(DP[N][0], DP[N][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2:\n",
    "            return nums[0]\n",
    "        dp = [0 for _ in range(len(nums))]\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return dp[len(nums)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # 自顶向下\n",
    "        # memo = [-1 for i in range(len(nums))]\n",
    "        # def dp(nums, start):\n",
    "        #     if start >= len(nums):\n",
    "        #         return 0\n",
    "\n",
    "        #     if memo[start] != -1:\n",
    "        #         return memo[start]\n",
    "        #     return max(dp(nums, start+1), nums[start] + dp(nums, start + 2))\n",
    "        # return dp(nums, 0)\n",
    "\n",
    "        # 自底向下\n",
    "\n",
    "        dp = [0 for i in range(len(nums) + 2)]\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            dp[i] = max(dp[i+1], nums[i] + dp[i+2])\n",
    "        return dp[0]\n",
    "\n",
    "        # 空间负责度优化到O(1)\n",
    "        dp_i = 0\n",
    "        dp_i_1 = 0\n",
    "        dp_i_2 = 0\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            dp_i = max(dp_i_1, nums[i] + dp_i_2)\n",
    "            dp_i_2 = dp_i_1\n",
    "            dp_i_1 = dp_i\n",
    "        return dp_i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return max(nums)\n",
    "        df = [0] * n\n",
    "        for i in range(n):\n",
    "            df[i] = nums[i] + max(df[i-3], df[i-2])\n",
    "        return max(df[-2:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        if l==1:  # 只有一间，只能盗窃这一间\n",
    "            return nums[0]\n",
    "        dp = [0]*l\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2, l):\n",
    "            dp[i] = max(dp[i-1], dp[i-2]+nums[i])\n",
    "        return dp[-1]\n",
    "\n",
    "        # @cache\n",
    "        # def dp(i):\n",
    "        #     \"\"\"\n",
    "        #     到第i间房能偷窃的最高金额\n",
    "        #     \"\"\"\n",
    "        #     if i<0:\n",
    "        #         return 0\n",
    "        #     return max(dp(i-1), dp(i-2)+nums[i])  # 盗窃前面的略过当前；当前隔间和当前\n",
    "        \n",
    "        # l = len(nums)\n",
    "        # return dp(l-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(dp[i-2] + nums[i], dp[i-1])\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2:\n",
    "            return nums[0]\n",
    "        dp = [0 for _ in range(len(nums))]\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return dp[len(nums)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*(n+1)\n",
    "        dp[1] = nums[0]\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = max(dp[i-2]+nums[i-1],dp[i-1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        elif n == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        else:\n",
    "            dp[0] = nums[0]\n",
    "            dp[1] = max(nums[1], nums[0])\n",
    "            for i in range(2, n):\n",
    "                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])\n",
    "            return dp[n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 目标: 用递归的思路解开\n",
    "        # 选或不选的DP\n",
    "        # x表示索引\n",
    "        @cache\n",
    "        def dfs(x:int) ->int:\n",
    "            if x < 0:\n",
    "                return 0\n",
    "            return max(dfs(x-2)+nums[x], dfs(x-1))\n",
    "\n",
    "        return dfs(len(nums)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # n = len(nums)\n",
    "        # @cache\n",
    "        # def dfs(i, is_rob):\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "        #     res = dfs(i - 1, 0)\n",
    "        #     if is_rob == 0:\n",
    "        #         res = max(res, dfs(i - 1, 1) + nums[i])\n",
    "        #     return res\n",
    "        # return dfs(n - 1, 0)\n",
    "\n",
    "        # n = len(nums)\n",
    "        # f = [[0] * 2 for _ in range(n + 1)]\n",
    "        # for i, x in enumerate(nums):\n",
    "        #     f[i + 1][0] = max(f[i][0], f[i][1] + nums[i])\n",
    "        #     f[i + 1][1] = f[i][0]\n",
    "        # return f[n][0]\n",
    "\n",
    "        n = len(nums)\n",
    "        f0 = f1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            f0, f1 = max(f0, f1 + x), f0\n",
    "        return f0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 2)\n",
    "        for i, x in enumerate(nums):\n",
    "            f[i + 2] = max(f[i + 1], f[i] + x)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        #dp[i]=max(dp[i-1],dp[i] + nums[i])\n",
    "        #dp[i] #截止到i前所能得到的最大数\n",
    "        n=len(nums)\n",
    "        dp=[0]*(n+1)\n",
    "        dp[0]=0\n",
    "        dp[1]=nums[0]\n",
    "        for i in range(2,len(nums)+1):\n",
    "            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        dp =[0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i==0:\n",
    "                dp[i] = nums[0]\n",
    "            elif i==1:\n",
    "                dp[i] = max(nums[0],nums[1])\n",
    "            else:\n",
    "                dp[i] = max(dp[i-2]+nums[i],dp[i-1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = nums[0]\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        dp = []\n",
    "        dp.append(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            if i == 1:\n",
    "                c = max(dp[i-1],nums[i])\n",
    "                dp.append(c)\n",
    "            else:\n",
    "                d = max(dp[i-1],dp[i-2]+nums[i])\n",
    "                dp.append(d)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*(n+2)\n",
    "        for i in range(n):\n",
    "            dp[i+2]=max(dp[i+1],dp[i]+nums[i])\n",
    "        i=n-1\n",
    "        while i>=0:\n",
    "            if dp[i+2]==dp[i]+nums[i]:\n",
    "                i-=2\n",
    "            else:\n",
    "                i-=1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        elif n == 2:\n",
    "            return max(nums)\n",
    "\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 目标: 用递归的思路解开\n",
    "        # 选或不选的DP\n",
    "        # x表示索引\n",
    "        # @cache\n",
    "        # def dfs(x:int) ->int:\n",
    "        #     if x < 0:\n",
    "        #         return 0\n",
    "        #     return max(dfs(x-2)+nums[x], dfs(x-1))\n",
    "\n",
    "        # return dfs(len(nums)-1)\n",
    "\n",
    "        # 递归转递推\n",
    "        f = [0] * (len(nums) + 2)\n",
    "        for i, x in enumerate(nums):\n",
    "            f[i + 2] = max(f[i + 1], f[i] + x)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = nums[0]\n",
    "        if n >= 2:\n",
    "            dp[1] = max(nums[0:2])\n",
    "            for i in range(2,n):\n",
    "                dp[i] = max(dp[i-2]+nums[i], dp[i-1])\n",
    "\n",
    "        return dp[n-1]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        @cache        \n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            return max(dfs(i-1), dfs(i-2) + nums[i])\n",
    "        return dfs(len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # 自顶向下\n",
    "        # memo = [-1 for i in range(len(nums))]\n",
    "        # def dp(nums, start):\n",
    "        #     if start >= len(nums):\n",
    "        #         return 0\n",
    "\n",
    "        #     if memo[start] != -1:\n",
    "        #         return memo[start]\n",
    "        #     return max(dp(nums, start+1), nums[start] + dp(nums, start + 2))\n",
    "        # return dp(nums, 0)\n",
    "\n",
    "        # 自底向下\n",
    "        dp = [0 for i in range(len(nums) + 2)]\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            dp[i] = max(dp[i+1], nums[i] + dp[i+2])\n",
    "\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        l = [0 for i in range(len(nums)+1)]\n",
    "        for i in range(len(nums)):\n",
    "            l[i+1] = max(l[i], l[i-1]+nums[i])\n",
    "        return l[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        if len(nums)==1:return nums[0]\n",
    "        dp=[[0,0] for i in range(len(nums))]\n",
    "        dp[0][0]=0#不偷第一家\n",
    "        dp[0][1]=nums[0]#偷第一家\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i][0]=max(dp[i-1][0],dp[i-1][1])\n",
    "            dp[i][1]=dp[i-1][0]+nums[i]\n",
    "        return max(dp[len(nums)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0: return 0\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                dp[0] = nums[0]\n",
    "            elif i == 1:\n",
    "                dp[1] = max(nums[0], nums[1])\n",
    "            else:\n",
    "                dp[i] = max(dp[i-1], dp[i-2] + nums[i]) \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 2)\n",
    "        for i in range(n):\n",
    "            f[i + 2] = max(f[i + 1], f[i] + nums[i])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "选或不选\n",
    "选：dfs(i+2)\n",
    "不选：dfs(i+1)\n",
    "max(dfs[i+2]+value[i],dfs[i+1]) \n",
    "'''\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            return max(dfs(i-1), dfs(i-2) + nums[i])\n",
    "        return dfs(len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return max(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[:2])\n",
    "\n",
    "        for i in range(2,n):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "money_dict=dict()\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        length =len(nums)\n",
    "        pre = 0\n",
    "        curr = 0\n",
    "        for i in range(length):\n",
    "            next_num = max(pre+nums[i],curr)\n",
    "            pre = curr\n",
    "            curr = next_num\n",
    "        return curr\n",
    "    \n",
    "    \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "    \n",
    "        dp = [0]*n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2,n):\n",
    "            dp[i] = max(dp[i-1], dp[i-2]+nums[i])\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f0 = f1 = 0\n",
    "        for i in range(n):\n",
    "            f1, f0 = max(f1, f0 + nums[i]), f1\n",
    "        return f1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 2)\n",
    "        for i in range(n):\n",
    "            f[i + 2] = max(f[i + 1], f[i] + nums[i])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        cur, pre = 0, 0 \n",
    "        for x in nums:\n",
    "            cur, pre = max(pre+x, cur), cur\n",
    "        return cur\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        j = k = 0\n",
    "        for x in nums:\n",
    "            i = max(k, j+x)\n",
    "            j, k = k, i\n",
    "        return k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        size=len(nums)\n",
    "        if size == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        first,second=nums[0],max(nums[0],nums[1])\n",
    "        for i in range(2,size):\n",
    "            first,second=second,max(first+nums[i],second)\n",
    "        \n",
    "        return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        # 定义状态: dp[i]表示从第i间房子开始抢劫，最多能抢到的金额\n",
    "        dp = [0 for i in range(N)]\n",
    "\n",
    "        for i in range(N-1, -1, -1):\n",
    "            if i == N-1:\n",
    "                dp[i] = nums[i]\n",
    "            elif i == N-2:\n",
    "                dp[i] = max(nums[i], nums[i+1])\n",
    "            else:\n",
    "                dp[i] = max(dp[i+1], nums[i] + dp[i+2])\n",
    "\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res = max(dfs(i-1),dfs(i-2)+nums[i])\n",
    "            return res\n",
    "        return dfs(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        ans = dp[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = nums[i]\n",
    "            if i - 2 >= 0: dp[i] = max(dp[i], dp[i-2] + nums[i])\n",
    "            if i - 3 >= 0: dp[i] = max(dp[i], dp[i-3] + nums[i])\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def rob(self, nums: list[int]) -> int:\n",
    "        l = len(nums)\n",
    "        dp = nums[:]\n",
    "        for i in range(2,l):\n",
    "            dp[i]+=max(dp[i-2::-1])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        dp[0][1] = nums[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])\n",
    "            dp[i][1] = dp[i - 1][0] + nums[i]\n",
    "\n",
    "        return max(dp[-1][0], dp[-1][1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])\n",
    "        return dp[n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 目标: 用递归的思路解开\n",
    "        # 选或不选的DP\n",
    "        # x表示索引\n",
    "        # @cache\n",
    "        # def dfs(x:int) ->int:\n",
    "        #     if x < 0:\n",
    "        #         return 0\n",
    "        #     return max(dfs(x-2)+nums[x], dfs(x-1))\n",
    "\n",
    "        # return dfs(len(nums)-1)\n",
    "\n",
    "        # 递归转递推\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        if n == 2:\n",
    "            return max(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = nums[1]\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(dp[i-2]+nums[i], dp[i-1], dp[i-3]+nums[i])\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # 好像可以是个动归\n",
    "        # 前k个的最大值\n",
    "        # 选择k 加上 k-2的最大值\n",
    "        # 不选择k 那就不用管\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        res = [0] * len(nums)\n",
    "        res[0] = nums[0]\n",
    "        res[1] = nums[1]\n",
    "\n",
    "        for i in range(2, len(nums)):\n",
    "            if i-3 >= 0:\n",
    "                res[i] = max(res[i-2], res[i-3]) + nums[i]\n",
    "            else:\n",
    "                res[i] = res[i-2] + nums[i]\n",
    "        \n",
    "        return max(res[-2:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        # out=[0]*n\n",
    "        \n",
    "        if n ==1:\n",
    "            return nums[0]\n",
    "        # if n==2:\n",
    "        #     return max(nums[0],nums[1])\n",
    "        max_num_i,out=0,[nums[0]]\n",
    "        # if n==2:\n",
    "        #     max_num_i=0\n",
    "        for i in range(1,n):\n",
    "            out+=[max(max_num_i+nums[i],out[i-1])]\n",
    "            max_num_i=max(max_num_i,out[i-1])\n",
    "        return out[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://mp.weixin.qq.com/s/z44hk0MW14_mAQd7988mfw\n",
    "# 线性数组\n",
    "\n",
    "# 方法一：备忘录，\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        memo = [-1] * len(nums)\n",
    "        return self.robby(nums, memo, 0)\n",
    "    \n",
    "    def robby(self, nums, memo, start):\n",
    "        # base case\n",
    "\n",
    "        # 这里是>=，不是==, 是因为start的最后一个值为N-1,此时start+1=n，start+2=n+1\n",
    "        if start >= len(nums): # 由下面的start+2决定的start边界值\n",
    "            return 0\n",
    "        \n",
    "        if memo[start] != -1:\n",
    "            return memo[start]\n",
    "        \n",
    "        res = max(self.robby(nums, memo, start+1), nums[start] + self.robby(nums, memo, start+2))\n",
    "        memo[start] = res\n",
    "\n",
    "        return memo[start]\n",
    "\n",
    "\n",
    "# # 方法二：节约空间\n",
    "# class Solution:\n",
    "#     def rob(self, nums: List[int]) -> int:\n",
    "#         if not nums:\n",
    "#             return 0\n",
    "#         if len(nums) == 1:\n",
    "#             return nums[0]\n",
    "            \n",
    "#         dp_i_1, dp_i_2 = 0, 0\n",
    "\n",
    "#         dp_i = 0\n",
    "#         for i in range(len(nums)):\n",
    "#             dp_i = max(dp_i_1, nums[i] + dp_i_2)\n",
    "#             dp_i_1, dp_i_2 = dp_i, dp_i_1\n",
    "        \n",
    "#         return dp_i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        \n",
    "        def process(k:int)->int:\n",
    "            if k<0:\n",
    "                return 0\n",
    "            return max(process(k-2)+nums[k],process(k-1))\n",
    "        return process(len(nums)-1)\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            # [i,n]\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            # 不选i dfs(i+1)\n",
    "            # 选i dfs(i+2)\n",
    "\n",
    "            return max(dfs(i+1), nums[i] + dfs(i+2))\n",
    "        return dfs(0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
